import java.util.Random;

//三路快速排序
public class QuickSort3 {
    private QuickSort3() {
    }

    public static <E extends Comparable<E>> void sort3ways(E[] arr) {
        Random rnd = new Random();
        sort3ways(arr, 0, arr.length - 1, rnd);
    }


    //分区 首先需要知道分区后标定点左边的数要比标定点小，标定点右边的数要比标定点大
    public static <E extends Comparable<E>> void sort3ways(E[] arr, int l, int r, Random rnd) {
        //arr[l+1---j] <=v   arr[j+1---i] >=v
        //作为标定点
        if (l >= r) {
            return;
        }
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr, l, p);
        //arr[l+1,lt] < v  arr[lt+1,gt-1] = v  arr[gt,r] > v
        //lt部分比p小，gt部分比p大，lt+1到gt-1部分等于p
        int lt = l, gt = r;
        int i = l + 1;
        while (i < gt) {
            //如果标定点后面的元素比标定点小，lt指针后移，交换lt和i指向的元素位置
            if (arr[i].compareTo(arr[l]) < 0) {
                lt++;
                swap(arr, i, lt);
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                gt--;
                swap(arr, i, gt);
            } else {
                i++;
            }
        }
        //arr[l,lt-1] < v  arr[lt,gt-1] = v  arr[gt,r] > v
        swap(arr, l, lt);
        sort3ways(arr, l, lt - 1, rnd);
        sort3ways(arr, gt, r, rnd);
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
